package com.sean.sort;

import java.util.Arrays;

/**
 * 交换排序：冒泡排序，快速排序
 */
public class SwapSort {
    /**
     * 冒泡排序
     * @param array: 待排序的数组
     */
    public static void bubbleSort(int[] array){
        long start = System.nanoTime();
        if(array.length <= 1){
            return;
        }
        for(int i = 0; i < array.length - 1; i ++){
            boolean isSwap = false;
            for(int j = array.length - 1; j > i; j--){
                if(array[j] < array[j - 1]){
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    isSwap = true;
                }
            }
            if(!isSwap){
                return;
            }
        }
        long end = System.nanoTime();
        System.out.println("冒泡排序用时： " + (end - start) + "ns");
    }

    /**
     * 快速排序
     * @param array： 待排序数组
     */
    public static void quickSort(int[] array){
        long start = System.nanoTime();
        if(array.length <= 1){
            return;
        }
        sort(array, 0, array.length - 1);
        long end = System.nanoTime();
        System.out.println("快速排序用时： " + (end - start) + "ns");
    }

    /**
     * 快速排序 —— 排序
     * @param array 待排序数组
     * @param left 待排序数组的左边界（闭区间）
     * @param right 待排序数组的有边界（闭区间）
     */
    private static void sort(int[] array, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            int temp = array[mid];
            array[mid] = array[right];
            array[right] = temp;
            mid = split(array, left, right);
            sort(array, left, mid - 1);
            sort(array, mid + 1, right);
        }
    }

    /**
     * 快速排序 —— 拆分
     * @param array 待拆分数组
     * @param left 数组左边界（闭区间）
     * @param right 数组有边界（闭区间）
     * @return 切割点
     */
    private static int split(int[] array, int left, int right){
        int temp = array[right];
        while (left < right){
            while(left < right && array[left] <= temp){
                left++;
            }
            if(left < right){
                array[right] = array[left];
                right--;
            }
            while(left < right && array[right] >= temp){
                right--;
            }
            if(left < right){
                array[left] = array[right];
                left++;
            }
        }
        array[left] = temp;
        return left;
    }

    public static void main(String[] args) {
        final int _10w = 100000;
        
        // 冒泡排序用时： 6050773300ns
        int [] test1 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test1[j] = i;
        }
        SwapSort.bubbleSort(test1);
        
        // 快速排序用时： 8653700ns
        int [] test2 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test2[j] = i;
        }
        SwapSort.quickSort(test2);
    }
}
